public class union_find extends union_find_v0{
    public int weight[];
    public union_find(int number)
    {
        super(number);
        weight=new int[number];
        for(int i=0;i<number;i++)  //初始化
        {
         weight[i]=1;
        }
    }

    public int root(int a)
    {
        if (this.a[a] != a) {
            this.a[a] = root(this.a[a]); // 路径压缩：直接指向根节点
        }
        return this.a[a];
    }
    public boolean connected(int a,int b)
    {
        if(a>=this.a.length||b>=this.a.length)
        {
            System.out.printf("输入越界！");
            return true;
        }
        return (root(a)==root(b));
    }
    public void union(int a,int b)
    {
        int root_a=root(a);
        int root_b=root(b);
        if(root_a==root_b)
        {
            return ;
        }
        else
        {
            if(weight[root_a]>weight[root_b])
            {
               this.a[root_b]=root_a;
            }
            else if(weight[root_a]<weight[root_b])
            {
                this.a[root_a]=root_b;
            }
            else
            {
                this.a[root_b]=root_a;
                weight[root_a]++;
            }
        }
    }
}
